//
// Created by Administrator on 2021/8/11.
//
//给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int> &nums) {
        // 空间复杂度o(n)
        unordered_map<int, int> um;
        for (const int &x:nums) {
            ++um[x];
        }
        int n = (int) nums.size() / 3;
        vector<int> ans;
        for (auto &x:um) {
            if (x.second > n)
                ans.push_back(x.first);
        }
        return ans;
    }
};

class Solution2 {  // 摩尔投票
public:
    //摩尔投票 总之 超过n/k的至多只有k-1个
    vector<int> majorityElement(vector<int> &nums) {
        int candidate1, candidate2; // 两个候选
        int count1 = 0, count2 = 0;
        int n = nums.size();
        // 投票
        for (int i = 0; i < n; i++) {
            if (nums[i] == candidate1) {
                count1++;
            } else if (nums[i] == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = nums[i];
                count1++;
            } else if (count2 == 0) {
                candidate2 = nums[i];
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        // 计数
        count1 = count2 = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == candidate1) {
                count1++;
            }
            if (nums[i] == candidate2) {
                count2++;
            }
        }
        vector<int> ans;
        if (count1 > (n / 3)) {
            ans.push_back(candidate1);
        }

        if (count2 > (n / 3)) {
            ans.push_back(candidate2);
        }
        return ans;
    }
};

int main() {
    vector<int> nums{3, 2, 3};
    Solution solution;
    vector<int> ans = solution.majorityElement(nums);
    for (const int &x:ans) cout << x << endl;
    return 0;
}
